package com.xxy.linklist;

/**
 * @author xxy
 * @create 2020 10 29 10:05
 * 约瑟夫问题：（单向环形链表）
 * 1.先创建一个节点，让first指向该节点，并形成环形
 * 2.后面当我们创建一个新的节点，就把giant节点，加入到已有的环形链表中
 * 3.遍历环形链表
 *   1.先让一个复制的指针变量指向first
 *   2.然后通过一个while循环就可以
 */
public class Josepfu {
    public static void main(String[] args) {
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.addBoy(5);
        circleSingleLinkedList.showBoy();
        circleSingleLinkedList.countBoy(1,2,5);
    }
}
//创建环形单向链表
class CircleSingleLinkedList{
    //创建第一个first节点，当前么有编号
    private Boy first = new Boy(-1);
    public void addBoy(int nums){
        if(nums<1){
            System.out.println("nums应该大于1");
            return;
        }
        Boy curBoy = null;
        for(int i =1;i<=nums ;i++){
            Boy boy = new Boy(i);
            //如果是第一个节点，
            if(i==1){
                first=boy;
                first.setNext(first);//构成环
                curBoy = first;
            }else {
                curBoy.setNext(boy);
                boy.setNext(first);
                curBoy=boy;
            }
        }
    }
    //遍历环形链表
    public  void showBoy(){
        //先构建一个辅助节点，指向first
        if(first==null){
            System.out.println("链表为空");
            return;
        }
        Boy auxiliaryBoy = first ;
        while(true){
            System.out.println("编号"+auxiliaryBoy.getNo());
            if(auxiliaryBoy.getNext()==first){
                break;
            }
            auxiliaryBoy=auxiliaryBoy.getNext();
        }
    }
    /**
     *约瑟夫出圈顺序
     * @param startNo 表示第几个小孩开始数数
     * @param countNum 表示数几下
     * @param nums 表示最初有多少小孩在圈中
     */
    public void countBoy(int startNo,int countNum,int nums){
        if(first ==null||startNo<1||startNo>nums){
            System.out.println("参数输入有问题！！");
            return;
        }
        //创建一个辅助节点,让其指向环形链表的最后一个节点
        Boy helper = first;
        while (true){
            if(helper.getNext()==first){
                break;
            }else {
                helper = helper.getNext();
            }
        }
        //小孩报数时，先让first和helper移动k-1次
        for(int j =0;j< startNo-1;j++){
            first=first.getNext();
            helper=helper.getNext();
        }
        while (true){
            if(helper==first){
                break;
            }//如果只有一个时，就结束
            for(int j=0;j<countNum-1;j++){
                first=first.getNext();
                helper=helper.getNext();
            }//这时，first指向的节点，就是要出圈的节点
            System.out.println("出圈"+first.getNo());
            first=first.getNext();
            helper.setNext(first);
        }
        System.out.println("最后留在圈中的编号"+first.getNo());
    }
}
//创建一个boy类，表示一个节点
class Boy {
    private int no;
    private Boy next;
    public Boy(int no){
        this.no= no;
    }
    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }
    public Boy getNext() {
        return next;
    }
    public void setNext(Boy next) {
        this.next = next;
    }
}
